Đầu vào của bài toán là một hàm (thực thi bởi hộp đen) f : { 0 , 1 } n → { 0 , 1 } n {\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}} , coi như thỏa mãn điều kiện với một số s ∈ { 0 , 1 } n {\displaystyle s\in \{0,1\}^{n}} ta có với mọi y , z ∈ { 0 , 1 } n {\displaystyle y,z\in \{0,1\}^{n}} , f ( y ) = f ( z ) {\displaystyle f(y)=f(z)} khi và chỉ khi y = z {\displaystyle y=z} or y ⊕ z = s {\displaystyle y\oplus z=s} . Chú ý rằng trường hợp s = 0 n {\displaystyle s=0^{n}} cũng được chấp nhận, tương ứng với f {\displaystyle f} là một hoán vị. Vấn đề cần giải quyết là tìm s.

Tập của các xâu n-bit là một không gian vec tơ Z 2 {\displaystyle \mathbb {Z} _{2}} dưới thao tác bit XOR. Giả sử hàm gốc của f hoặc rỗng, hoặc tạo nên các tập-hợp-chung có n-1 chiều. Sử dụng các thuật toán lượng tử, ta có thể, với xác suất cao, xác định được các véc tơ cơ sở sinh ra n-1 không gian con này, vì s là véc tơ vuông góc với toàn bộ các véc tơ cơ sở trên.

Hàm lượng tử trong thuật toán Simon

Xét không gian Hilbert chứa đựng tích ten-xơ của không gian Hilbert của các xâu đầu vào, và cho ra đầu ra là các xâu. Sử dụng biến đổi Hadamard, ta có thể tạo trạng thái ban đầu

∑ x | x ⟩ | 0 ⟩ {\displaystyle \sum _{x}\left|x\right\rangle \left|0\right\rangle }

và gọi hộp đen để chuyển trạng thái này thành

∑ x | x ⟩ | f ( x ) ⟩ {\displaystyle \sum _{x}\left|x\right\rangle \left|f(x)\right\rangle }

Biến đổi Hadamard chuyển trạng thái trên thành

∑ y ∑ x ( − 1 ) x . y | y ⟩ | f ( x ) ⟩ {\displaystyle \sum _{y}\sum _{x}(-1)^{x.y}\left|y\right\rangle \left|f(x)\right\rangle }

Ta thực hiện đo cùng lúc ở cả hai thanh ghi. Nếu s ⋅ y = 1 {\displaystyle s\cdot y=1} , ta nhận được sự giao thoa giảm. Vậy, chỉ không gian con s ⋅ y = 0 {\displaystyle s\cdot y=0} là được chọn. Thử với một số lượng y, ta có thể tìm được n-1 véc tơ cơ sở, và tính s.